//
//  test.c
//  刷题
//
//  Created by 仲7 on 2024/11/22.
//
#include"test.h"
//1——查询并计数从 2 到 n 的质数
int countPrimes(int n) {
    //处理 1 和 0 的特殊情况
    if(n == 1 || n == 0)
    {
        return 0;
    }
    //创建一个变长数组，为其申请动态空间，初始值均置为0（意为默认全是质数）
    int isPrime[n];
    memset(isPrime,0,sizeof(isPrime));
    //然后遍历从 2 到 n 的所有数，并在循环中判断是否为质数，和标记质数的倍数为合数
    //定义一个计数变量
    int count = 0;
    for(int i = 2;i < n;++i)
    {
        //判断是否为质数，若为质数则计数一次
        if(!isPrime[i])
        {
            count++;
            //继续遍历该质数的倍数，把质数的倍数全部标记为合数
            //防止整形 i 的平方超过int 的最大值，所以要把 i 转化为长整型进行相乘再与 n 进行比较
            //if((long long)i * i < n)
            //{
                for(long long j = (long long)i * i;j < n;j += i)
                //此时 j 不能用 int 型接收后面长整型的 i 的平方，不然超过 int 的最大范围后，这个值会被截断，或者变成一个负值，导致下面的数组调用下标时，出现越界。
                {
                    isPrime[j] = 1;//标记为合数
                }
            //}
        }
    }
    //最后返回质数个数
    return count;
}
